package org.kk.ds.linked;

/**
 * @author kk
 * @Date 2021/2/4
 */
public class DoubleLinked {
    private Node head,tail;
    private int length;
    public DoubleLinked(){
        this.head = new Node(-1);
        this.tail = new Node(-1);
        this.head.next = tail;
        this.tail.pre = head;
        this.length = 0;
    }
    public int size(){
        return length;
    }
    public boolean isEmpty(){
        return length == 0;
    }
    public void addAtTail(int value){
        Node t = tail.pre;
        Node newNode = new Node(t,value, tail);
        tail.pre = newNode;
        t.next = newNode;
        length++;
    }
    public void addAtHead(int value){
        Node newNode = new Node(head,value,head.next);
        head.next = newNode;
        head.next.next.pre = newNode;
        length++;
    }
    public void add(int index, int value) {
        checkElementIndex(index);
        if (index == size()) {
            addAtTail(value);
        } else{
            linkBefore(value, node(index));
        }
    }
    private void linkBefore(int value, Node x){
        final Node pred = x.pre;
        final Node newNode = new Node(pred,value,x);
        x.pre = newNode;
        pred.next = newNode;
        length++;
    }
    private Node node(int index){
        Node x;
        if (index < (size() >> 1)) {
            x = head.next;
            for (int i = 0; i < index; i++)
                x = x.next;
        } else {
            x = tail.pre;
            for (int i = size() -1; i > index; i--)
                x = x.pre;
        }
        return x;
    }
    public int get(int index){
        checkElementIndex(index);
        Node node = node(index);
        return node.value;
    }
    public void remove(int index){
        checkElementIndex(index);
        remove(node(index));
    }
    public void removeKey(int key){
        for(Node x = head.next; x != null && x.next != tail; x = x.next){
            if(key == x.value){
                remove(x);
            }
            x = x.next;
        }
    }
    private void remove(Node x){
        Node pre = x.pre;
        Node next = x.next;
        if(next == null){
            tail.pre = pre;
            pre.next = tail;
        }else{
            pre.next = next;
            next.pre = pre;
        }
    }
    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
        Node node = head;
        builder.append("[");
        while(node != null && node.next != tail){
            builder.append(node.next.value);
            node = node.next;
            builder.append("->");
        }
        builder.delete(builder.length() -2, builder.length());
        builder.append("]");
        return builder.toString();
    }
    private void checkElementIndex(int index){
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size();
    }
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size();
    }
    class Node{
        private int value;
        Node pre,next;
        Node(int value){
            this.value = value;
        }
        Node (Node pre, int value, Node next){
            this(value);
            this.pre = pre;
            this.next = next;
        }
    }
}